from typing import List

class Solution:
    def removeElement(self, nums, val):
        """
        方法一：双指针
        移除数组中值为val的元素，返回新数组的长度
        
        Args:
            nums: 输入数组
            val: 要移除的值
            
        Returns:
            int: 移除元素后数组的新长度
            
        Time: O(n) - 其中 n 是数组的长度
        Space: O(1) - 只使用了常数额外空间
        """
        left = 0
        for right in range(len(nums)):
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
        return left

    def removeElement1(self, nums, val):
        """
        方法二：双向双指针（优化版本）
        当要删除的元素很少时，这种方法更优
        
        Args:
            nums: 输入数组
            val: 要移除的值
            
        Returns:
            int: 移除元素后数组的新长度
            
        Time: O(n) - 其中 n 是数组的长度
        Space: O(1) - 只使用了常数额外空间
        """
        left = 0
        right = len(nums)
        
        while left < right:
            if nums[left] == val:
                # 将最后一个元素移到当前位置
                nums[left] = nums[right - 1]
                right -= 1
            else:
                left += 1
        return left


def main():
    """
    主函数，用于测试 Solution 类的方法
    """
    solution = Solution()
    
    # 测试用例 1: 常规情况
    print("测试用例 1:")
    nums1 = [3, 2, 2, 3]
    val1 = 3
    print(f"原始数组: {nums1}")
    result1 = solution.removeElement(nums1, val1)
    print(f"移除 {val1} 后的长度: {result1}")
    print(f"处理后的数组前 {result1} 个元素: {nums1[:result1]}\n")

    # 测试用例 2: 空数组
    print("测试用例 2:")
    nums2 = []
    val2 = 1
    print(f"原始数组: {nums2}")
    result2 = solution.removeElement(nums2, val2)
    print(f"移除 {val2} 后的长度: {result2}")
    print(f"处理后的数组: {nums2}\n")

    # 测试用例 3: 所有元素相同
    print("测试用例 3:")
    nums3 = [1, 1, 1, 1]
    val3 = 1
    print(f"原始数组: {nums3}")
    result3 = solution.removeElement1(nums3, val3)
    print(f"移除 {val3} 后的长度: {result3}")
    print(f"处理后的数组前 {result3} 个元素: {nums3[:result3]}\n")

    # 测试用例 4: 没有要移除的元素
    print("测试用例 4:")
    nums4 = [1, 2, 3, 4]
    val4 = 5
    print(f"原始数组: {nums4}")
    result4 = solution.removeElement1(nums4, val4)
    print(f"移除 {val4} 后的长度: {result4}")
    print(f"处理后的数组: {nums4[:result4]}")


if __name__ == "__main__":
    main()